#define  _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


void AdjustDown(Heap* hp, int parent)
{
	assert(hp);

	int child = 2 * parent + 1;
	while (child < hp->_size)
	{
		if (child + 1 < hp->_size && hp->_a[child + 1] > hp->_a[child])
			child++;
		if (hp->_a[child] > hp->_a[parent])
		{
			swap(&hp->_a[child], &hp->_a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}

void AdjustUp(Heap* hp, int child)
{
	assert(hp);

	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (hp->_a[child] > hp->_a[parent])
		{
			swap(&hp->_a[child], &hp->_a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void CheckCapacity(Heap* hp)
{
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity == 0 ? 10 : 2 * hp->_capacity;
		HPDataType* np = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (!np)
		{
			perror("malloc");
			exit(-1);
		}
		hp->_a = np;
		hp->_capacity = newcapacity;
	}
}

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->_a == NULL)
	{
		assert(hp->_a);
		return;
	}
	memcpy(hp->_a, a, sizeof(HPDataType) * n);
	 hp->_size = n;
	 hp->_capacity = n;
	 for (int root = (n - 1 - 1) / 2; root >= 0; root--)
	 {
		 AdjustDown(hp, root);
	 }
}

void HeapDestory(Heap* hp)
{
	assert(hp);

	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}




void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	CheckCapacity(hp);

	hp->_a[hp->_size++] = x;
	AdjustUp(hp, hp->_size-1);
}

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	AdjustDown(hp, 0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	int ret = hp->_a[0];
	return ret;
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}